import java.util.*;

public class day4 {
    /**
     * NC138 矩阵最长递增路径
     * https://www.nowcoder.com/practice/7a71a88cdf294ce6bdf54c899be967a2?tpId=196&tqId=37184&ru=/exam/oj
     */
    int n,m;
    int[][] memo = new int[1001][1001]; // 判断这个位置是否到过，并且还有步数

    public int solve (int[][] matrix) {
        n = matrix.length;
        m = matrix[0].length;

        for(int i = 0;i < n;i++) {
            for(int j = 0;j < m;j++) {
                memo[i][j] = -1;
            }
        }

        int ret = 0;
        for(int i = 0;i < n;i++) {
            for(int j = 0;j < m;j++) {
                ret = Math.max(ret,dfs(matrix,i,j));
            }
        }
        return ret;
    }

    int[] dx = {1,-1,0,0};
    int[] dy = {0,0,1,-1};
    // 返回的就是步数
    public int dfs(int[][] matrix,int i,int j) {
        // 记忆化搜索，进行优化
        if(memo[i][j] != -1) {
            return memo[i][j];
        }

        int len = 1;
        for(int k = 0;k < 4;k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if(x >= 0 &&  x < n && y >= 0 && y < m && matrix[x][y] > matrix[i][j]) {
                len = Math.max(len,1 + dfs(matrix,x,y));
            }
        }

        memo[i][j] = len;
        return len;
    }



    /**
     * kotori和迷宫
     * https://ac.nowcoder.com/acm/problem/50041
     */
    public static int n,m;
    public static char[][] arr = new char[31][31];
    public static int[][] disit = new int[31][31];
    public static int x1,y1;

    public static void main3(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        for(int i = 0;i < n;i++) {
            char[] s = in.next().toCharArray();
            for(int j = 0;j < m;j++) {
                arr[i][j] = s[j];
                if(arr[i][j] == 'k') {
                    x1 = i;
                    y1 = j;
                }
            }
        }
        for(int i = 0;i < n;i++) {
            for(int j = 0;j < m;j++) {
                disit[i][j] = -1;
            }
        }

        dfs(x1,y1,0);

        int count = 0,ret = 1000;
        for(int i = 0;i < n;i++) {
            for(int j = 0;j < m;j++) {
                if(arr[i][j] == 'e' && disit[i][j] != -1) {
                    count++;
                    ret = Math.min(ret,disit[i][j]);
                }
            }
        }
        if(count > 0) {
            System.out.println(count + " " + ret);
        }else {
            System.out.println(-1);
        }
    }

    public static int[] dx = {0,0,1,-1};
    public static int[] dy = {1,-1,0,0};

    public static void dfs(int i,int j,int pos) {
        if(arr[i][j] == 'e') {
            disit[i][j] = pos;
            return;
        }

        for(int k = 0;k < 4;k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if(x >= 0 && x < n && y >= 0 && y < m && (arr[x][y] == 'e' || arr[x][y] == '.') && disit[x][y] == -1) {
                disit[x][y] = 1;
                dfs(x,y,pos + 1);
            }
        }
    }

    // bfs
    public static int N = 31;
    public static int n,m;
    public static int x1,y1;
    public static char[][] str = new char[N][N];
    public static int[][] visit = new int[N][N];

    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        for(int i = 0;i < n;i++) {
            char[] s = in.next().toCharArray();
            for(int j = 0;j < m;j++) {
                str[i][j] = s[j];
                if(str[i][j] == 'k') {
                    x1 = i;
                    y1 = j;
                }
            }
        }

        bfs();

        int count = 0,ret = 1000;
        for(int i = 0;i < n;i++) {
            for(int j = 0;j < m;j++) {
                if(str[i][j] == 'e' && visit[i][j] != -1) {
                    count++;
                    ret = Math.min(ret,visit[i][j]);
                }
            }
        }
        if(count > 0) {
            System.out.println(count + " " + ret);
        }else {
            System.out.println(-1);
        }
    }
    public static int[] dx1 = {1,-1,0,0};
    public static int[] dy1 = {0,0,-1,1};

    public static void bfs() {
        for(int i = 0;i < n;i++) {
            for(int j = 0;j < m;j++) {
                visit[i][j] = -1;
            }
        }

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x1,y1});
        visit[x1][y1] = 0;

        while(!queue.isEmpty()) {
            int[] t = queue.poll();
            int a = t[0];
            int b = t[1];
            for(int k = 0;k < 4;k++) {
                int x = a + dx[k];
                int y = b + dy[k];
                if(x >= 0 && x < n && y >= 0 && y < m &&
                        str[x][y] != '*' && visit[x][y] == -1) {
                    visit[x][y] = visit[a][b] + 1;
                    if(str[x][y] != 'e') {
                        queue.add(new int[]{x,y});
                    }
                }
            }
        }
    }



    /**
     * BC76 ISBN号码
     * https://www.nowcoder.com/practice/95712f695f27434b9703394c98b78ee5?tpId=290&tqId=39864&ru=/exam/oj
     */
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        char[] s = in.next().toCharArray();

        int sum = 0,count = 1,n = s.length;
        // 把标识符去掉，之后计算那9个数字
        for(int i = 0; i < n - 1;i++) {
            if(s[i] >= '0' && s[i] <= '9') {
                sum += (s[i] - '0') * count;
                count++;
            }
        }

        int end = sum % 11;

        if(end == (s[n - 1] - '0') || (end == 10 && s[n - 1] == 'X')) {
            System.out.println("Right");
        }else {
            // 重新将最后一位赋值
            s[n - 1] = end == 10 ? 'X' : (char)(end + '0');
            for(int i = 0;i < n;i++) {
                System.out.print(s[i]);
            }
        }
    }
}
